1. Field of the Invention
The present invention relates to a motion vector detecting apparatus for coding images, reducing noise, tracing objects, etc.
2. Related Art of the Invention
A technique of motion vector detection on the basis of a time-space differentiating method has been already proposed, for example, as Horn's method (Horn, B. K. P. and B. G. Shunk: "Determining optical flow," Artificial Intelligence, Vol. 17, pp. 185-203, 1981). In this method, the brightness of point (x, y) on the image at time t is supposed to be I (x, y, t), and an object is assumed to move by .DELTA.x on the x-axis and by .DELTA.y on the y-axis-during infinitesimal time .DELTA.t. Assuming the brightness of the same point on the object to be constant, formula (1) is established. EQU I(x,y,t)=I(x+.DELTA.x,y+.DELTA.y,t+.DELTA.t) (1)
By Taylor series expansion of the right side of formula (1), higher order terms are ignored, and considering the extremity of .DELTA.t=0 by dividing by .DELTA.t, formula (2) is established. ##EQU1##
where u=d .DELTA.x/dt, v=d.DELTA.y/dt. Supposing (u, v) to be a velocity vector, it becomes a constraint equation by time-space differentiation. In this constraint equation, a straight line on which the motion vector. (u, v) can be determined from the time-space differentiation of luminance, but a certain constraint is needed to determine (u, v). Horn, supposing that (u, v) changes smoothly on the image, applied a new constraint, and determined the motion vector. As a prior art of this detecting apparatus for a motion vector, its structural drawing is shown in FIG. 1. In FIG. 1, numeral 301 is an A/D converter, 302,303 are frame memories, 304 is a horizontal direction differentiating filter, 305 is a vertical direction diff erentiating filter, 306 is a time direction differentiating filter, 307 is a horizontal direction differential image memory, 308 is a vertical direction differential image memory, 309 is a time direction differential image memory, 310 is a horizontal direction motion memory, 311 is a horizontal direction motion estimating part, 312 is a vertical direction motion estimating part, 313 is a vertical direction motion memory, and 314,315 are smoothing filters.
The image entered through the A/D is delayed by 1 frame time in the frame memory 302, and sequentially passes through the frame memory 303.
The horizontal direction differentiating filter 304, vertical direction differentiating filter 305, and time direction differentiating filter 306 calculate thetime-space differentiation (.differential.I/.differential.x, .differential.I/.differential.y, .differential.I/.differential.t) of formula (2) necessary for estimation of. the motion vector in each pixel.
The calculation results are respectively recorded in the horizontal direction differential image memory 307, vertical direction differential image memory 308, and time direction differential image memory 309.
Since the image is sampled, the calculation of differentiation is replaced by calculation;of a difference method.
Horn, supposing that (u,.v) changes smoothly on the image, determined the motion vector in a form of minizing formula (3). EQU E=.intg..intg..alpha..sup.2 ((u,v)-(u,v)).sup.2 +(uI.sub.x +vI.sub.y +I.sub.t).sup.2 dxdy (3)
Hereinafter, for the sake of simplicity, (.differential.I/.differential.x, .differential.I/.differential.y, .differential.I/.differential.t) is expressed as (Ix, Iy, It). Minimization of formula (3) can be solved by the repetition shown iin formula (4) in a form of solving the Euler-Lagrange equation obtained by partial differentiation of the formula (3). Herein, (u, v) is the vicinity average of motion vector, k is the number of repetitions, and .alpha. is a constant. EQU u.sup.k+1 +u.sup.k -Ix(I.sub.x u.sup.k +I.sub.y v.sup.k +I.sub.t)/(.alpha..sup.2 +Ix.sup.2 +I.sub.y.sup.2) EQU v.sup.k+1 +v.sup.k -Iy(I.sub.x u.sup.k +I.sub.y v.sup.k +I.sub.t)/(.alpha..sup.2 +Ix.sup.2 +I.sub.y.sup.2) (4)
(U.sub.k+1, V.sub.k+1) in formula (4) is calculated respectively in the horizontal direction motion estimating part 311 and the vertical direction motion estimating part 312, and restored in the horizontal direction motion memory 310 and the vertical direction motion memory 313.
The vicinity average necessary for calculation is calculated by the smoothing filters 314, 315. Thus, according to this conventional detecting apparatus for a motion vector, the motion vector can be determined by motion estimation and vicinity smoothing.
In the foregoing prior art, however, the following problems are present:
(1) Repeated calculations of more than scores of times are generally needed, and the processing time is long; PA1 (2) Smoothing is necessary for determining the vicinity average, and hence different motion vectors near the boundary of the object are smoothed and are not determined accurately; and PA1 (3) The estimation error is large on the boundary of the object. PA1 (a) a memory for holding video signals which are coded and composed of frame units, PA1 (b) a horizontal differentiating filter for reading out luminance data from the memory and differentiating (executing a differential method) or differencing (executing a difference method) in a horizontal direction of arbitrary image coordinates, PA1 (c) a vertical differentiating filter for reading out luminance data from the memory and differentiating or differencing in the vertical direction of the image coordinates, PA1 (d) a time differentiating-filter for reading out the luminance data of preceding and succeeding frames from the memory, and differentiating or differencing in a time direction, PA1 (e) feature vector combining the means for combining luminance differential vector (Ix, Iy, It) including the results of the horizontal differentiating filter, the vertical differentiating filter and the time differentiating filter, and the position vector (x, y) of the image coordinates, to obtain a sample vector, (f) a memory for holding a plurality of an estimation of a motion vector (u, v) and a position vector mean (x, y) of the sample vector as class data, PA1 (g) nearest class determining means for determining a distance between the class data and the sample vector from a formula (x-x, y-y) and a formula (u*Ix+v*Iy+It), and achieving a correspondence between the sample vector and nearest class data, and PA1 (h) class data changing means for changing the class data in a manner that a distance sum between the class data and one or more sample vectors becomes smaller, from one or more sample vectors and the class data of which correspondence has been achieved by the nearest class determining means.
The second and third problems are due to the mutual dependence of the estimation of the motion vector and region segmentation of the image. For estimation of the motion vector, certain coupling with a framework of region segmentation is required.